package LeetCode刷题.暑假刷的算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-27 10:39
 * @description: Functions of this class is
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 **/
public class 字符串的排列 {
    public static void main(String args[]) {
        System.out.println(Arrays.toString(permutation("abc")));
    }

    public static String[] permutation(String s) {
        List<List<Character>> tot = new ArrayList<>();
        char s1[] = new char[s.length()];
        for (int i = 0; i < s.length(); i++) {
            s1[i] = s.charAt(i);
        }
        dfs(0, s.length(), s1, tot);
        String ans[]=new String[tot.size()];
        for(int i=0;i<tot.size();i++){
            String ss="";
           for(int j=0;j<tot.get(i).size();j++){
               ss+=tot.get(i).get(j);
           }
           ans[i]=ss;
        }
        return ans;
    }

    private static void dfs(int index, int right, char s1[], List<List<Character>> tot) {
        if (index == right) {
            List<Character> sub = new ArrayList<>();
            for (char c : s1) {
                sub.add(c);
            }
            if (!tot.contains(sub)) {
                tot.add(sub);
            }
            return;
        }
        for (int i = index; i < right; i++) {
            swap(s1, i, index);
            dfs(index + 1, right, s1, tot);
            swap(s1, i, index);
        }
    }

    private static void swap(char nums[], int i, int j) {
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}